package com.likeycy.my.list;

/**
 * @ClassName: MyArrayListUpgradeFirstVersion
 * @Description: MyArrayList第二版升级
 * 主要改造：1.增加根据对象删除
 *         2.增加动态缩容
 *         3.删除元素时动态缩容
 *         4.移除元素时动态缩容为默认初始长度
 * @Author: sodagreen
 * @Date: 2021/2/21 8:02
 * @Version: 1.0
 */
@SuppressWarnings("unchecked")
public class MyArrayListUpgradeSecondVersion<E> {

    /**
     * 在每次添加或删除的时候保存当前集合内有多少个元素数量，如果没有添加进来元素，则默认为0
     */
    private int size;
    /**
     * 所有元素存储的数组容器
     */
    private E[] elements;
    /**
     * 指定存储元素的数组长度，当创建实例没有指定长度时默认为该长度
     */
    private static final int DEFAULT_CAPACITY = 10;

    private static final int ELEMENT_NOT_FOUND = -1;

    /**
     * 无参数构造器,当对象实例化调用该构造意味着开发者未指定集合初始化长度，这里默认指定集合初始化长度
     */
    public MyArrayListUpgradeSecondVersion() {
        this(DEFAULT_CAPACITY);
    }

    /**
     * 有参构造器，指定初始化数组的容量
     *
     * @param capacity 容量
     */
    public MyArrayListUpgradeSecondVersion(int capacity) {
        // 如果指定的容量为0或者是一个负数，此时不应该直接实例化，而应该判断
        capacity = capacity > 0 ? capacity : DEFAULT_CAPACITY;
        this.elements = (E[]) new Object[capacity];
    }

    /**
     * 获取集合内元素的总数量
     *
     * @return
     */
    public int size() {
        // 直接返回size属性
        return size;
    }

    /**
     * 判断集合是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        /*
         判断集合是否为空，可以用size是否为0来判断这个集合是不是空集合。而不能用 elements.length()
         因为 elements有可能被实例化后并没有添加元素，但 elements数组已经有了固定长度。如果拿数组长度来判断，
         肯定是不对的。length为10的空数组，怎么都比0要大。而如果用循环遍历来判断，那更浪费了。所以此处用size最适合
         如果size==0，返回ture，集合为空。反之不为空
         */
        return size == 0;
    }

    /**
     * 判断集合内是否包含某个元素
     *
     * @param element
     * @return
     */
    public boolean contains(E element) {
        // 这个功能其实和indexOf做的事情是相似的，我们完全可以用indexOf方法来做。
        int index = indexOf(element);
        // 然后判断一下索引是不是大于-1。如果集合没有这个元素，indexOf会返回-1,如果有会返回索引值。记住这个规则
        return index != ELEMENT_NOT_FOUND;
    }

    /**
     * 添加元素到集合
     *
     * @param element
     */
    public void add(E element) {
        /*
          添加元素是添加到集合的尾部。如果集合实例化，还没有添加过元素。那就是从索引为0的位置开始添加元素。
          此时索引值0与size是相等的。因为集合实例化，size默认的初始值就为0。且每次添加元素到集合，size都需要做累加动作。
          即 size++。这也就意味着，每次添加元素是该元素的索引值都和size相等。代码表示为：
          elements[size] = element;
          size++;
          此时我们可以简化以上代码，在添加完元素后，然size累加。
          elements[size++] = element;
          添加第1个元素：elements[0++] = value1; index=0; add后size++ = 1
          添加第2个元素：elements[1++] = value1; index=1; add后size++ = 2
          添加第3个元素：elements[2++] = value1; index=2; add后size++ = 3
          ……
         */
        /*elements[size++] = element;*/
        add(size, element);
    }

    /**
     * 获取指定索引位置的元素并返回
     *
     * @param index
     * @return
     */
    public E get(int index) {
        /*
         这里根据索引取集合内元素处有一个问题。那就是索引不能为负数或者是超过集合的长度。
         假设实例化后的集合长度为默认的10，其只存了10个元素。调用该方法，传进来一个 -10 或者 11，索引值不在集合 0-9
         的范围内，这时候程序还能运行下去吗？所以这里需要判断一下
         */
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index:" + index + "，Size:" + size);
        }
        return elements[index];
    }

    /**
     * 向指定的索引位置插入元素
     *
     * @param index
     * @param element
     * @return
     */
    public E set(int index, E element) {
        // 这里传入的index也可能会遭遇索引值超出集合范围的问题，所以需要判断
        rangeCheck(index);
        // 添加一个元素到指定的索引位置，只需要 elements[index] = element即可。但是我们还需要返回旧的元素
        E oldValue = elements[index];
        elements[index] = element;
        return oldValue;
    }

    /**
     * 向集合内指定位置插入元素，原索引位置的所有元素都需要往后移动一位
     *
     * @param index
     * @param element
     */
    public void add(int index, E element) {
        // 首先还是要先判断索引是否为负数越界
        rangeCheckForAdd(index);

        /*
          当集合原有长度都存储满了元素，下一次再添加新元素，此时应该要保证数组进行动态的扩容，有足够的长度来存储元素
          所以我们需要判断下一次的索引是否超过了当前数组的长度，如果超过了，则需要进行扩容。未雨绸缪
         */
        ensureCapacity(size + 1);

        // 在指定位置插入元素前，需要将指定位置及其之后的元素都往后移动一位。最佳方法就是从最后面的元素开始挪动
        for (int i = size - 1; i >= index; i--) {
            elements[i + 1] = elements[i];
        }
        elements[index] = element;
        size++;
    }

    /**
     * 删除指定索引位置的元素并返回被删除的元素
     *
     * @param index
     * @return
     */
    public E remove(int index) {
        /*
          删除元素需要注意一件事，无论是根据元素删除还是根据索引值删除，被删除的元素后继节点的元素都要向前挪动
          比如说，集合内有5个元素，分别是[10, 11, 12, 13, 14]。如果传入的索引值为2，则要删除掉12这个元素节点。
          同时，还需要将索引为3(元素13)和索引为4(元素14)的两个节点向前挪动，同时size也需要累减，即size--
          可不可以不挪动后面的节点？这里我列举两个场景：
          一：设计时remove元素不挪动后继节点，只删除后做size--。那问题来了，添加时由于size是用来绑定要添加元素索引位置的。
          新元素就会覆盖size索引值的旧元素。这样不就造成数据丢失了吗？
          二：设计师remove元素不挪动后继节点，size--操作也不做。那么会出现长度为10的集合，存10个元素，删除4个，剩6个。
          此时size为10.这时往集合再次添加一个元素，由于没有往前挪动节点空出来4个多余节点内存空间，无法被利用，所以需要扩容，把
          它存储索引值为10的位置。这样不是浪费了内存吗？到时候集合越大，删除操作做的越大，不是会出现仅几个元素占用成千上万的内存空间么？
          所以删除元素时，需要挪动后继元素往前靠，腾出内存空间。同时size--
         */
        rangeCheck(index);
        E removeVal = elements[index];
        for (int i = index + 1; i < size; i++) {
            elements[i - 1] = elements[i];
        }
        size--;
        /*
          当改造为泛型后，remove方法也需要进行改变。因为有这么一个场景。假设elements数组有存储了3个Object元素，此时，删除了索引值为0的元素。
          意味着后面索引值为1和2的Object元素需要往前挪。1挪到0位置，2挪到1位置。由于是复制，此时索引值为2的节点，依然还存在着一个对象元素的地址值。
          只不过是把索引值为2的对象元素地址值复制到索引值为1的节点挪动。如果不清空,对象会一直被强引用无法被回收，且清空操作需要在size--之后操作。
         */
        elements[size] = null;
        // 以上两句可以合成一句 elements[--size] = null;
        trimToSize();
        return removeVal;
    }

    /**
     * 根据对象删除集合内的元素
     * @param element
     * @return
     */
    public boolean remove(E element) {
        /*
          这里其实有两个场景：
          1、传进来的对象在集合中只有一个，那直接删除
          2、如果传进来的对象在集合中有多个，怎么办？删除遍历到的第一个元素。也就是不管里面多少重复的对象，只删除找到的第一个就好了。
          3. 如果传入的对象是一个null怎么办
            该方法其实和根据索引删除元素是一样的，都是找到元素在集合内哪个索引位置，然后删除。之后将排在该元素后面的元素往前挪
            其实我们已经实现了查找元素在集合内索引位置的功能，也实现了根据索引删除的功能，所以我们只要组合一下就能实现了
         */
        return remove(indexOf(element)) != null;
    }

    /**
     * 动态缩小容量
     */
    public void trimToSize() {
        // 如果删除后内存空间占用过大，且当前实例并未必使用，可以考虑动态缩小该实例占用的内存空间
        int currentCapacity = elements.length;
        int newCapacity = currentCapacity >> 2;
        // 如果当前元素总数量小于数组总空间长度的一半，且当前数组空间长度小于或者等于默认集合容量，则不处理
        if (size >= newCapacity || currentCapacity <= DEFAULT_CAPACITY) {
            return;
        } else {
            E[] newElements = (E[]) new Object[newCapacity];
            for (int i = 0; i < size; i++) {
                newElements[i] = elements[i];
            }
            elements = newElements;
            System.out.println(currentCapacity + "-缩容为-" + newCapacity);
        }

    }

    /**
     * 确保数组能够动态扩容，有足够的长度能不断的添加新元素进来。而扩容也需要讲究方法。扩容不能太小，也不能太大。需要取
     * 折中的方式。所以我们按照Java官方ArrayList指定的1.5倍来扩容。
     *
     * @param capacity 容量
     */
    private void ensureCapacity(int capacity) {
        // 首先拿到旧的容量
        int oldCapacity = elements.length;
        // 判断旧的容量是否小于下一次要添加元素所需要的容量。如果为true，表示已经不满足需要扩容
        if (oldCapacity < capacity) {
            // oldCapacity >> 1 等同于 oldCapacity / 2
            // 右移是除以2^n,左移是乘以2^次方
            // 8 << 1 = 8 * 2 = 16; 8 << 2 = 8 * 2 * 2 = 32
            // 8 >> 1 = 8 / 2 = 4; 8 >> 2 = 8 / 2 / 2 = 2
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            // 创建一个新的数组，容量是之前数组的1.5倍，并且将之前旧容量数组的数组复制到新数组里面
            E[] newElements = (E[]) new Object[newCapacity];
            for (int i = 0; i < size; i++) {
                newElements[i] = elements[i];
            }
            // 复制完成后则将成员属性elements指向新容量数组
            elements = newElements;

            System.out.println(oldCapacity + "-扩容为-" + newCapacity);
        }
    }

    /**
     * 由于多个方法会抛出同一个异常，这里将异常封装为一个方法进行复用
     *
     * @param index
     */
    private void outOfBounds(int index) {
        throw new IndexOutOfBoundsException("Index:" + index + "，Size:" + size);
    }

    /**
     * 检查传入的索引是否越界，如果越界，抛出异常
     *
     * @param index
     */
    private void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            outOfBounds(index);
        }
    }

    /**
     * 检查添加元素时传入的索引是否越界，如果越界，抛出异常
     *
     * @param index
     */
    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size) {
            outOfBounds(index);
        }
    }

    /**
     * 查看元素在集合内所处的索引值，如果元素不存在，返回-1
     *
     * @param element
     * @return
     */
    public int indexOf(E element) {
        /*
          改造为泛型后，indexOf也需要改造一下。因为有可能传入null值。且我们设计的ArrayList集合是允许存储空值得。如果该集合中有多个null值，
          那我们就需要判断一下，返回第一个查找到的null值得索引位置即可
         */
        if (element == null) {
            for (int i = 0; i < size; i++) {
                if (elements[i] == null) {
                    return i;
                }
            }
        } else {
            /*
             这里需要注意，如果查找的元素不在集合里，那么要返回一个指定的数。不一定为-1，你也可以指定为-10。
             这只是个约定俗成的规则。
             */
            for (int i = 0; i < size; i++) {
                /*
                  这里的equals比较对那些基本数据类型和已重写了equals方法的类有效。equals方法在Object中的默认实现就是等同于 ==比较。
                  当一个对象没有重写equals方法时，此时两个对象相比较的是他们的内存地址值，而不是对象内部属性的各项值。所以如果传入了一个对象，
                  判断传入的对象在集合中是不是存在，请将该实例的类重写equals方法。否则，equals判断的就若同 object1 == object2。将永远
                  返回false
                 */
                if (element.equals(elements[i])) {
                    return i;
                }
            }
        }
        // 可以直接写成-1，或者把-1变成常量，尽量使用常量。
        return ELEMENT_NOT_FOUND;
    }

    /**
     * 清除所有元素
     */
    public void clear() {
        /*
         当进行泛型改造之后，数据元素存储的都是对象类型了。此时在一个场景中出现了一个问题。
         当elements属性长度确定，向内存空间申请一块连续内存。用来存储对象，此时elements数组里面的每个节点存储的是每个对象的地址值，而不是
         对象本身。这很好理解，比如说一个对象有很多成员属性，实例化一个对象的时候需要N多个字节空间才能存放。如果此时整个对象都被装载在数组容器
         的每个节点里，那么这个数组将会变得庞大无比。一个节点就要占用N多个字节，而基本类型最高也才8个字节而已。而且后续还可能不断扩容，内存是
         无法负担的。所以每个节点实际上存储的是对象的地址值，来指向对象在堆内存的哪个位置。也就是常说的引用，或者叫指针。
         现在，当我们将集合清空了，可是elements数组的每个节点保存的数据元素地址值依然指向着内存中的实例化对象。而垃圾回收器发现该对象还被内存中
         其它的对象指向着，就不会回收。然而这些对象实际上又可能是没有被任何使用者使用了。导致了内存空间被占用，迟迟无法释放，还可能导致OOM。
         所以，我们需要显式的给elements数组的每个节点赋值为null，断开与那些已经没有使用的对象的联系，让GC工作，收回内存。
         毕竟再次添加新元素到集合里，那么肯定是new了一个新的对象，有了一个新的地址值，不会和之前的相同了。
         */
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }

        /*
         清除元素有几种方案：
         1. 重新创建一个数组。这样可以做但是浪费内存。创建新数组需要申请内存空间，旧的也还在内存里等待垃圾回收
         2. 设置集合对象为null。但如果使用者清空后还需要用，此时为null的集合对象调用添加元素的方法岂不是会空指针
         3. 直接将size变为0。
         第三种是最好的办法。当size赋值为0，之前集合无论存了多少数据，你再传任意索引值进来获取元素，在调用相关方法时候都会
         有对索引值进行判断: if (index < 0 || index >= size) 。很明显，当你传入任意索引值都无法通过这个判断，因为size=0。所以只会抛出异常
         这里，我们需要转一个角度来看问题。不使用使用者的眼光来看，而是用框架设计者的眼光来看。
         */
        size = 0;
        if (elements != null && elements.length > DEFAULT_CAPACITY) {
            elements = (E[]) new Object[DEFAULT_CAPACITY];
        }
    }

    /**
     * 返回数组的字符串形式
     *
     * @return
     */
    @Override
    public String toString() {
        // 如果我们不重写toString方法，打印数组的字符串时会是一串内存地址值，而不是数组里面的内容
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("MyArrayList{size=").append(size).append(", elements=[");
        for (int i = 0; i < size; i++) {
            // 判断元素是否为第一个，不是第一个的时候拼接一个逗号
            if (i != 0) {
                stringBuilder.append(", ");
            }
            stringBuilder.append(elements[i]);
        }

        return stringBuilder.append("]}").toString();
    }
}
